package algorithms.other;

/**
 * 汉诺塔问题解法
 * 
 * 把n个自顶向下从小到大的盘子借助C柱从A柱移动到B柱，任何时候不能有大的盘子在小的盘子之上
 * 
 * 使用递归直到移动的盘子数为一
 * 
 * @author syx
 *
 */
public class TowerOfHanoi {
	/**
	 * 思路是要将最底下的盘子移动到B，首先要将n-1个盘子移动到C，任何将盘子n移动到B，最后将n-1个盘子移动到B，这是个递归过程
	 * 
	 * 到只需要移动一个盘子的时候，就只需要移动一次
	 * 
	 * @param n
	 * @return
	 */

	static int move(int n) {
		if (n <= 1) {
			return n;
		} else {
			// return move(n - 1) + move(1) + move(n - 1);
			return 2 * move(n - 1) + 1;
		}
	}

	public static void main(String[] args) {
		System.out.println(move(3));
		System.out.println(move(4));
		System.out.println(move(5));
		System.out.println(move(6));
	}

}
